The invention relates generally to font technology and, more specifically, to an improved scan conversion system for supplying a character bitmap defining pixels to be activated on pixel-oriented display devices.
Most general purpose computer systems support a display of text-based characters, including letters, numerals, and other symbols, on pixel-oriented display devices. A pixel is a discrete segment of an overall field in which an image can be displayed. Although pixels are typically square or round in shape for most devices, many newer pixel-oriented display devices include rectangular pixels. A pixel is activated or xe2x80x9cturned onxe2x80x9dwhen the process that generates the display determines that it is appropriate to activate that portion of the image field. Accordingly, the display surface for a pixel-oriented display device consists of a grid of points, or pixels, each of which can be individually illuminated or xe2x80x9cdarkenedxe2x80x9d to display an image. Common pixel-oriented display devices are raster scan cathode ray tube (CRT) displays, liquid crystal display (LCD) displays, dot matrix printers, and laser printing devices.
In general, to display text on a pixel-oriented display device, a computer system utilizes one or more fonts. A font is a collection of characters designed by a typographer in a consistent style. Specifically, a typographer designs a character outline or xe2x80x9cglyphxe2x80x9d of each character for a particular font, including characters, numbers, punctuation, and any other image for a given font. A particular font refers to selected geometric characteristics of the characters within a character set. A glyph for a given character in a font is described as a numbered sequence of points that are on or off a curve defining the boundary of the character. In general, number sequence for the points should follow a recognized rule for how the points relate to the area to be filled and the area not to be filled when rendering the glyph. For TrueType font descriptions, the points are numbered in consecutive order so that as a path is traversed in the order of increasing point numbers, the filled area will always be to the right of the path. This glyph or outline description of the character is typically stored within a font file maintained by the computer system. TrueType font files are described in the Technical Specification, Revision 1.5, January 1994, entitled xe2x80x9cTrueType 1.0 Font Files,xe2x80x9d by Microsoft Corporation, Redmond, Wash.
In response to the information supplied by a font file, the outline is scaled according to the font size requested by the user and the characteristics of the display device on which it is to be displayed. The outline also may contain hints, which are routines that, when executed, adjust the shapes of the character outlines for various point sizes to improve their appearance. The outline is then scan converted to produce a character bitmap that can be rendered on the selected display device.
A character bitmap represents a grid-like array of pixels and each array element contains a pixel center. The pixel centers are connected in either horizontal or vertical directions by straight lines commonly described as scan lines or reference lines. Each character bitmap contains data reflecting which pixels in a subset of the display grid must be illuminated in order to form an image of a particular character. When a computer system needs to display a particular character at a display location, it accesses the character bitmap for that character. The computer system then turns the illumination of pixels near the display location on or off in accordance with the data stored in the character bitmap. The concept of displaying a character extends to a temporary display, such as a CRT display, as well as a more permanent image creation in the form of a printer.
Using font descriptions, computer systems can now create character bitmaps defining the images to be displayed, also described as raster fonts, dynamically in different typefaces in response to the needs of users. A computer program, which is also described as a rasterizer program, is typically incorporated as part of an operating system or printer control software program to provide this font technology service. The rasterizer program may be called by an application program, such as a word processor or a spreadsheet, when the program requires a raster font. In response to this request, the rasterizer program reads a description of the character outline from a font file stored within a memory storage device. The font file can be stored within either volatile or nonvolatile memory of the computer system or the display device.
The rasterizer program also receives the character""s height or xe2x80x9cpointxe2x80x9d size and the predetermined resolution of the intended display device to support the scaling of the character outline. The resolution of a pixel-oriented display device is specified by the number of dots or pixels per inch (dpi) that are to be displayed. This information supports a mapping of the description of the character outline into physical pixel units for the display device to be employed in displaying the character in that particular size. Thus, the geometric description of the character outline is scaled in physical pixel coordinates and represents a function of the predetermined physical pixel size of the display device and the requested point size. This process alters the height and width of the character.
To support the rendering of fonts at low resolution and/or small sizes, the rasterizer program typically includes a routine that analyzes the outlines of fonts and xe2x80x9chintsxe2x80x9d the fonts according to the size specified by the user in the resolution of the display device. The fundamental task of hinting is to identify critical characteristics of the original font design and to use instructions which adjust the outline to insure that those characteristics will be preserved when the character outline is rendered in different sizes on different dev,ices. Common hinting goals include consistent stem weights, consistent intensity, even spacing, and the elimination of pixel dropouts.
If required, the rasterizer program applies hints to the scaled character outline to fit it to pixel boundaries while distorting the scaled character outline as little as possible. The rasterizer program thereafter conducts a scan conversion operation for the hinted character outline by superimposing a grid corresponding to the horizontal and vertical densities of the intended display device over the hinted outlines, then designating the subset of pixels of the grid whose centers fall within, or precisely on, the hinted outlines as pixels requiring illumination by the display device. The rasterizer program then returns the resulting raster font to the application program, which may use it to display text. The raster font also may be stored within an allocated buffer of computer system memory or display device memory to be used to satisfy any identical request received in the future.
The scan conversion process represents the task of xe2x80x9ccoloringxe2x80x9d inside the lines of the character. For the rasterizer program, a scan converter generates a character bitmap which includes pixels which are activated based upon the relationship of the pixel centers with the character outlines. For conventional scan converters, two rules are generally used to determine if a particular pixel should be turned on or turned off. First, if a pixel""s center or reference point falls within the character outline, that pixel is turned on and becomes part of that character outline. Second. if a contour of the character outline falls exactly on a pixel""s center, that pixel is turned on. These rules define the conventional xe2x80x9ccenterpointxe2x80x9d fill method of bitmapping a character outline or glyph and is well known in the art of digital typography.
In general, at the start of a conventional scan conversion process, the character outline is traversed to determine the maximum and minimum coordinate values of the outline. The amount of memory required for the computer system to support the scan conversion tasks is then estimated to insure sufficient workspace memory for the storage of calculation results generated by the rendering operation. Each contour of the character outline is subsequently broken into individual segments of lines and splines and these segments are rendered. The rendering process detects each occurrence of an intersection of a scan line with one of the representations of a line segment or spline segment. Each scan line intersection represents a transition having a particular transition sense, i.e., an on-transition or an off-transition. For each detected transition, a transition entry containing the transition location is stored within a data array called a transition table. Depending upon the sense of the transition entry, the transition entry is stored within either the xe2x80x9cONxe2x80x9d transition table or the xe2x80x9cOFFxe2x80x9d transition table. These transition entries are typically sorted by ascending order of the scan lines to support the creation of a character bitmap. Each transition having an xe2x80x9cONxe2x80x9d sense is paired with its corresponding transition having an xe2x80x9cOFFxe2x80x9d sense and the pixels associated with the scan line are set or xe2x80x9cfilledxe2x80x9d for the character bitmap. The character bitmap defines the pixels to be activated for supplying an image of the character on a connected display device.
Reviewing now certain aspects of the scan conversion process, one method for estimating the amount of workspace memory to support scan conversion tasks is to multiply the number of scan lines in the character bitmap times the maximum possible intersections of a character outline per scan line. The maximum possible intersections per scan line is calculated by traversing the character outline and counting the character""s local maxima and minima, which are also described as xe2x80x9creversalsxe2x80x9d in direction. Although this method represents a simple computational solution for the memory estimate, it supplies an overly conservative estimate of workspace memory for character outlines with small details. Accordingly, there is a need for an improved method that defines a more efficient use of memory to support scan conversion tasks. The present invention provides an improved method for allocating memory workspace by accurately calculating memory requirements. for character outlines with either large details or many small details, thereby supporting the efficient use of this computer resource.
The use of splines to represent outline curves is known in font technologies. One technique for rendering a spline is to break it into short line segments and then to render those segments sequentially by using a parametric equation to define the short line segments. However, the use of a parametric equation to render a spline supplies only an approximate representation of the actual curve. In addition, to obtain a reasonably accurate approximation, a large number of line segments must be used to represent the character outline. This increases the number of calculations, thereby increasing the time required to render the spline. Accordingly, there is a need in the art for a method of rendering splines that is both faster and more accurate than the above-described conventional technique. The present invention implements an implicit rendering algorithm based on a second order equation for a parabola to achieve improvements in speed and character image quality.
In general, rendering a bounded character outline or shape produces for a given scan line both an on-transition and an off-transition based upon the entering and exiting intersections of the scan line with the character outline. However, the concept that a bounded shape intersects a given scan line in matched pairs of transitions breaks down when the scan line contacts extrema of the shape, or when an endpoint of the shape is coincident with scan lines. The present invention addresses the special case of rendering an endpoint on a scan line by supplying a structured approach that examines all geometric possibilities for approaching and exiting the endpoint to determine whether the pixel associated with the endpoint should be activated.
As pixel-oriented display devices have achieved higher resolution characteristics, it has become possible to display text in smaller-sized characters on these devices while still maintaining readability. However, as physical character size becomes smaller for a display device of a given resolution, sampling error distortion can occur. Accordingly, after making an initial determination for which pixels to turn on, the contour of the character outline is analyzed to detect one type of sampling error that commonly occurs when displaying characters of a given font on a pixel-oriented display device, an error called xe2x80x9cdropout.xe2x80x9d A dropout condition may be defined as an interior region of a character outline that passes through a scan line and between adjacent pixels in which neither pixel has been turned on in accordance with the previously described Rules 1 and 2. In other words, a dropout condition occurs when the space within the character outlines become so narrow that this contour portion misses one or more pixel centers.
If a dropout control technique is not used to correct the dropout condition, the decision-making algorithm for activating a pixel may determine that a particular pixel should not be activated, thereby causing a break at a point in a character that the viewer would expect to be a continuous line. Although this problem will naturally arise even if the physical size of the character to be displayed is rather large (if the resolution of the display device is low, or if the character features are very thin), it is mostly problematic when characters are to be displayed with a small physical size.
It is known that the subjective response of a reader to dropout is to prefer having a pixel illuminated, even if it tends to geometrically distort the character, over a situation in which an inappropriate discontinuity occurs in the strokes of the character. Therefore, the art has addressed the subject of dropout control so that the results in a displayed image is most pleasing to viewers. A conventional technique for addressing the dropout problem is to always activate the pixel on the left for a horizontal pair of pixels and, for a vertical pair of pixels, to always activate the pixel below. From a typographical view, this convention produces a less than desirable result. Another technique is to always illuminate the pixel located nearest the contour of the character outline. This generally provides a displayed image having an appearance preferred by viewers because it preserves the symmetry of the character outline. However, this approach requires knowledge and storage of intersections of the character outline with the scan lines, or transitions, in sub-pixel precision, thereby increasing the processing time and memory requirements for scan conversion. The present invention provides an improved solution for the dropout condition by reducing the number of calculations required to obtain sub-pixel accuracy for the rendering of line segments and splines.
In summary, the present invention provides an improved scan converter to support the efficient and accurate display of character outlines by pixel-oriented display devices. To conserve the finite resource of memory, the present invention supports an efficient use of available memory workspace by accurately determining an upper bound for the amount of memory required to support scan conversion calculations. To achieve improvements in speed and character image quality, the present invention renders the spline segments of a character outline by using a quadratic equation to calculate an implicit function based on the spline control points. The present invention further addresses in a systematic manner the rendering of an endpoint located on a scan line to determine whether the pixel associated with the endpoint should be activated. This decision is based upon the direction of approach to and exit from this endpoint for the pair of segments connected to the endpoint. The present invention also reduces the number of calculations requiring sub-pixel precision to support the selection of the pixel located nearest the contour, thereby providing an improved solution for dropout condition.
The present invention fulfills the above-described needs by providing an improved scan converter for efficiently and accurately generating character bitmaps that designate pixels to be activated for displaying character images on pixel-oriented display devices.
The rendering of a glyph uses a portion of computer memory as xe2x80x9cworkspacexe2x80x9d memory for the storage of rendering calculations and data results. A prior method for estimating the maximum amount of memory required to support these scan conversion operations is completed by multiplying the number of scan lines in the character bitmap times the maximum possible intersections of a character outline per scan line. However, for the rendering of characters having numerous contour reversals that occur over a small set of the total scan lines, this method typically produces an overly conservative estimate for the amount of required workspace memory.
Thus, the first aspect of the present invention provides a method for calculating a more accurate estimate of the maximum amount of workspace memory, thereby avoiding the inefficient use of the finite resource of computer memory. By traversing the boundary of a character outline or glyph, each local maximum or local minimum of the glyph can be detected and the sense for each of these reversals can be determined. A local maximum represents a contour reversal having a positive reversal sense and a local minimum represents a contour reversal having a negative reversal sense. The location of each detected local minimum and local maximum is defined in terns of the scan line number for the scan line associated with one or more of these reversals. It will be appreciated that local maxima and minima of a function can be located at points where the partial derivatives for the function are zero.
Upon detecting the location and the sense of each of the reversals for the glyph, a first sum is calculated for the scan line numbers associated with local minima, and a second sum is calculated for the scan line numbers associated with local maxima. The difference between the first and second sums is proportional to the required workspace memory allocation. Computer memory is allocated in proportion to this estimate of the maximum amount of required workspace memory.
For another aspect of the present invention, an improved method for rendering a spline is provided to support the scan conversion of a glyph. For a selected spline, each occurrence of an intersection of a scan line and the spline is defined by a non-parametric equation. Each intersection defines a transition and a corresponding transition sense of either a positive (xe2x80x9cONxe2x80x9d) sense or a negative (xe2x80x9cOFFxe2x80x9d) sense. The transition sense of each transition is determined by the location of the spline within the pixel grid, i.e., by the particular quadrant that the spline is located. Forward differencing is used to solve the non-parametric equation and to determine the location in pixel coordinates for each transition. This forward differencing technique supports a xe2x80x9cwalkxe2x80x9d along the contour of the spline to detect the transition(s). For each detected transition, a transition entry is placed in an appropriate transition table to support the subsequent filling of the character outline. Each transition entry can include the location of the transition in pixel-based coordinates and is stored in either of two types of storage arrays, an xe2x80x9conxe2x80x9d transition table or an xe2x80x9coffxe2x80x9d transition table, based upon the sense of the transition.
The improved spline rendering method uses a second order, non-parametric equation that models a parabola. This improved method reduces the number of calculations required for rendering a particular spline because prior rendering methods typically have used a third order, parametric equation to render an outline curve. Unlike these prior spline rendering methods, the improved method does not rely upon the iterative adjustment of the time parameter (t) to determine the intersections of the spline with a scan line. Instead, the improved method relies upon the calculation of coefficients based upon spline control points and an equation solution defined by the iterative adjustment of pixel coordinates. Thus, it will be appreciated that this implicit rendering algorithm of the present invention achieves performance improvements in speed and character image quality.
Focusing upon the details of the improved method for rendering a spline (and assuming that the option of dropout control is not selected), the spline is first divided as required into discrete representations of spline segments. One of the spline segments is selected and the location of the segment within the pixel grid is determined. If the selected segment is located in either the first or the second quadrants, then the xe2x80x9cONxe2x80x9d horizontal transition table is selected for storing the locations of horizontal transitions. These horizontal transitions are preferably stored by the corresponding horizontal scan line number in this transition table. In contrast, if the selected segment is located in the third or fourth quadrants, the horizontal transitions detected by this spline rendering method are stored in the xe2x80x9cOFFxe2x80x9d horizontal transition table.
If required, the selected segment is normalized by reflecting it within the first quadrant of the pixel grid. A non-parametric equation is then generated to describe the selected spline segment. This non-parametric equation is solved using an initial set of pixel coordinates (x, y) to produce a sum Q. The relationship of the sum Q to the value zero determines whether the point defined by the pixel coordinates is located outside, inside, or on the selected spline segment. In particular, if the sum Q is greater than zero, the point is outside the selected spline segment and, if the sum Q is less than zero, the point is inside the selected spline segment. The point represented by pixel coordinates is located on the selected spline segment if the sum Q is equal to zero.
In view of this relationship of the sum Q to the value zero, the value of the sum Q is tested to determine if it is greater than zero. If the sum Q is greater than zero, then an integer pixel unit is added to the xe2x80x9cxxe2x80x9d pixel coordinate value to generate a new set of the pixel coordinates. The non-parametric equation is then solved again using this new set of pixel coordinates to produce a new value of the sum Q, and the loop continues. In contrast, if the sum Q is less than or equal to zero, then this set of pixel coordinates is stored in the appropriate horizontal transition table to define a horizontal transition. This process, which is commonly described as forward differencing, is repeated on a pixel-by-pixel basis by xe2x80x9cwalkingxe2x80x9d the selected spline segment. Each step for which the sum Q is less than zero represents an intersection of the selected spline segment with a horizontal scan line at the location defined by the associated pixel coordinates.
The forward differencing process is repeated to complete the rendering of the selected segment and, in this manner, each segment of the spline is rendered.
For another aspect of the present invention, an improved method is provided for rendering a glyph having an endpoint located on a scan line. This improvement is intended for use with the type of scan conversion process that (1) detects each occurrence of an intersection of a scan line and a segment and (2) places the corresponding transition entry into a transition table in response thereto. First, an occurrence of an intersection of a centerpoint and a scan line is detected. A first segment representation and a second segment representation are connected at the centerpoint, which defines an endpoint for each of the first and second segment representations. An approach direction to the intersection for a first endpoint of the first segment representation and an exit direction from the intersection for a second endpoint of the second segment representation are then determined based upon the pixel coordinates for the corresponding adjacent endpoints.
A table is provided that defines transition sense entries for each combination of the values of the approach direction and the exit direction. Using the table, a particular transition sense entry associated with the values of the approach direction and the exit direction is located. This transition sense entry is useful for creating a transition entry for the centerpoint in a transition table. A transition sense entry may indicate zero, one, or two transition entries to be added to the transition tables. It will be appreciated that this table defines the transition sense entries for all possible approach and exit directions, thereby supporting an organized determination of the transition sense associated with the endpoint on the scan line.
For yet another aspect of the present invention, an improved method for controlling a dropout condition is provided for a scan conversion operation of the type that (1) detects each occurrence of an intersection of a scan line and a spline or a line segment, or an endpoint of one of these discrete segments, and (2) places a transition entry in the appropriate transition table in response thereto. This scan conversion process detects a potential dropout condition in response to a pair of transition entries having opposite transition sense values at the same location in the pixel grid. These transition entries are generated by first and second discrete segments crossing a particular scan line and extending between adjacent pixels to define a region that does not include a pixel center. The improved dropout control process determines, in sub-pixel coordinates, first and second scan-direction coordinates for respective intersections of the first and second discrete segments and the particular scan line. In particular, simultaneous linear equations for line segments and recursive subdivision for splines are used to recalculate with sub-pixel accuracy the locations of scan line intersections for the pair of adjacent pixels associated with the dropout condition. If the scan coordinates represent an endpoint of a contour segment on a scan line, then these pixel coordinates are used to define the scan line intersection. A pixel having the pixel center closest to a midpoint between the first and second scan-direction coordinates is determined and this pixel is subsequently activated. By reducing the number of time-intensive sub-pixel calculations, the present invention supplies improved dropout control performance.
Therefore, it is an object of the present invention to provide an improved method to efficiently use available memory by accurately determining an upper bound for the amount of workspace memory required to support scan conversion calculations.
It is a further object of the present invention to achieve improvements in speed and accuracy for the rendering of splines.
It is a further object of the present invention to provide an improved method for rendering spline segments of a character outline by using a second order non-parametric equation to calculate an implicit function based on the spline control points.
It is a further object of the present invention to provide an improved method for rendering an endpoint located on a scan line by determining whether the pixel associated with the endpoint should be activated based upon the direction of approach to and exit from the endpoint for the pair of segments connected to the endpoint.
It is a further object of the present invention to provide an improved method for controlling dropout conditions that reduces the number of calculations requiring sub-pixel precision to support the selection of the pixel having a pixel center located nearest the contour.
That the present invention achieves these objects and fulfills the needs described hereinabove will be appreciated from the detailed description to follow and the appended drawings.